package 极客算法训练营.chapter07;

public class 爬楼梯 {
    class Solution1 {
        public int climbStairs(int n) {
            if (n == 0 || n == 1) {
                return 1;
            }
            return climbStairs(n - 1) + climbStairs(n - 2);
        }
    }

    class Solution {
        public int climbStairs(int n) {
            int[] memo = new int[n + 1];//memo[0]是一个补充值，递归用到的是memo[1]到memo[n],所以需要用到n+1个值
            return climbMemo(n, memo);
        }

        public int climbMemo(int n, int[] memo) {
            //递归终止条件
            if (n == 0 || n == 1) {
                memo[n] = 1;
            }
            //添加缓存值
            if (memo[n] == 0) {
                memo[n] = climbMemo(n - 1, memo) + climbMemo(n - 2, memo);
            }
            //取缓存值
            return memo[n];
        }
    }
}
